/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-10 16:18:48
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-10 21:50:53
 * @FilePath: \LeetCode\322.零钱兑换.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=322 lang=cpp
 *
 * [322] 零钱兑换
 *
 * 方法1：子集树顺序穷举
 * - 运行超时
 *
 * 方法2：分治递归 + 动态规划
 * - 问题： min_count 不能设置为全局变量 -> 与递归直接相关
 *
 * 方法3：非递归动态规划
 * - 自底向上：子问题最优 -> 整体最优
 * - 状态转移方程：dp[i] = min{1 + dp[i-Vj]}, i:面值 Vj:第j个硬币面额, i >= Vj
     dp[0] = 0
     dp[1] = 1 + dp[1-1] = 1
     dp[2] = 1 + dp[2-1] = 2
     dp[3]:  1 + dp[3-1] = 1 + dp[2] = 3
             1 + dp[3-2] = 1 + dp[1] = 2
             1 + dp[3-3] = 1 + dp[0] = 1
 */

#include <vector>
#include <algorithm>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int len = 0;
    int m_amount = 0;
    int count = 0, min_count = std::numeric_limits<int>::max();

    void visitSubTree(const std::vector<int> &coins, int i)
    {
        if (m_amount == 0)
        {
            min_count = std::min(min_count, count);
            return;
        }

        for (int k = i; k < len; k++)
        {
            m_amount -= coins[k];
            count++;
            if (m_amount >= 0)
                visitSubTree(coins, k);
            m_amount += coins[k];
            count--;
        }
    }

    int coinChange_01(std::vector<int> &coins, int amount)
    {
        len = coins.size();
        m_amount = amount;

        visitSubTree(coins, 0);

        return (min_count == std::numeric_limits<int>::max()) ? -1 : min_count;
    }

    std::vector<int> bestCount;

    int getMinCount(const std::vector<int> &coins, int amount)
    {
        /* 递归结束 */
        if (amount == 0)
            return 0;
        else if (amount < 0)
            return -1;
        /* 子问题最优解 */
        if (bestCount[amount] != 0)
            return bestCount[amount];
        /* 选择不同的硬币 */
        int min_count = std::numeric_limits<int>::max();
        for (auto c : coins)
        {
            int count = getMinCount(coins, amount - c);
            if (count >= 0 && count < min_count)
                min_count = count + 1;
        }

        bestCount[amount] = (min_count == std::numeric_limits<int>::max()) ? -1 : min_count;
        return bestCount[amount];
    }

    int coinChange_02(std::vector<int> &coins, int amount)
    {
        bestCount.resize(amount + 1, 0);
        return getMinCount(coins, amount);
    }

    int coinChange_03(std::vector<int> &coins, int amount)
    {
        std::vector<int> bestCount(amount + 1, amount + 1); // 默认最值 amount + 1
        /* dp[i] = min{1 + dp[i-Vj]}, i >= Vj */
        bestCount[0] = 0;
        for (int i = 1; i <= amount; i++)
        {
            for (auto c : coins)
            {
                if (i >= c)
                    bestCount[i] = std::min((1 + bestCount[i - c]), bestCount[i]);
            }
        }

        return (bestCount[amount] > amount) ? -1 : bestCount[amount];
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> coins = {2};

    // std::cout << solution.coinChange(coins, 3) << std::endl;
    // for (auto n : solution.bestCount)
    //     std::cout << n << " ";
    // std::cout << std::endl;

    return 0;
}